- floating point comparison
- floating point addition
- floating point multiplication
- floating point division
- absolute value
- dot product (3D)
- cross product
- vector addition
Octree
Construction
- Check the relative position of the OBB representing a region with the AABB representing an octree cell:
- AABB fully outside
- Intersection
- AABB fully inside (intersection)
- Do this for all the regions of the cell:
- AABB fully inside OR fully outside all regions: cell is a leaf, save regions where the AABB is fully inside.
- At least one region intersects (not fully inside): recursively subdivide the cell (only consider the regions that intersect it).
- Do this until cells are too small or all cells are leaves.
- To check the relative position of an AABB and an OBB we must use the separating axis theorem (SAT), which is complex.
early out if SAT fails, but little gains (SAT is way the most complex part by far)
check AABB for OBB: we check if all the vertices of the AABB are inside the OBB of the region
approximate cost and many early outs
Traversal
- Find the octree cell of the point and look up the regions.
- The search in the octree is linear w.r.t. the max number of levels allowed for the octree.
for each axis we have to get if the component is before or after the half point
AABB for OBB
Construction
- For each vertex of each triangle, test if it is inside each BVH region.
- To check if it is inside:
- Check if a point is inside the AABB.
- Check if a point is inside the OBB:
- To do so, we basically have to transform the point in the coordinate system of the OBB.
early out if the AABB part fails
early out when one component doesn't satisfy the comparison (outside AABB)
there may be an early out if the first (or second) coordinate is already out of the OOBB
Traversal
- For each BVH region, we have to check if the point is inside.
Simplify to AABBs